최적 수송 Sinkhorn-Knopp 알고리즘

1. 서론

1.1 행렬 스케일링 문제의 역사적 배경과 중요성

본 안내서는 1960년대 Richard Sinkhorn과 Paul Knopp에 의해 연구된 Sinkhorn-Knopp 알고리즘에 대한 심층적 고찰을 제공한다.1 이 알고리즘은 본래 주어진 음이 아닌 정방 행렬(non-negative square matrix)을 특정 제약 조건을 만족하도록 변환하는 ‘행렬 스케일링(matrix scaling)’ 문제, 특히 이중 확률 행렬(doubly stochastic matrix)로 변환하는 문제를 해결하기 위해 제시되었다.2 이중 확률 행렬이란 모든 행의 합과 모든 열의 합이 1이 되는 행렬을 의미하며, 이러한 변환은 통계학에서의 비상계수표(contingency tables) 정규화, 경제학의 투입-산출(input-output) 표 분석, 웹 페이지 랭킹 등 다양한 분야에서 근본적인 중요성을 지녀왔다.1 알고리즘의 핵심은 행과 열을 번갈아 가며 목표 합계에 맞추어 정규화하는 매우 간단하고 직관적인 반복 과정에 있다.2 이 단순성에도 불구하고, 알고리즘이 언제 수렴하고 그 결과가 유일하게 존재하는지에 대한 수학적 조건은 깊은 이론적 탐구를 필요로 했다.

1.2 최적 수송 문제와의 연결을 통한 알고리즘의 부상

수십 년간 행렬 분석 및 통계학의 특정 분야에서 꾸준히 사용되던 Sinkhorn-Knopp 알고리즘은 21세기에 들어 계산 과학 분야에서 극적인 재조명을 받게 된다. 2010년대에 이르러, 이 알고리즘은 선형 계획법(Linear Programming)으로 정식화되는 고전적 최적 수송(Optimal Transport, OT) 문제의 엄청난 계산적 복잡성을 극복할 핵심 열쇠로 부상했다.1 최적 수송 문제는 한 확률 분포를 다른 확률 분포로 변환하는 데 필요한 최소 비용을 측정하는 이론으로, 그 응용 가능성이 무궁무진함에도 불구하고 O(n^3 \log n)에 달하는 계산 비용 때문에 대규모 데이터 분석에는 실용적으로 적용되기 어려웠다.4

이러한 상황을 타개한 돌파구는 최적 수송 문제에 ’엔트로피 정규화(entropic regularization)’라는 개념을 도입한 것이었다.4 이 정규화는 원래의 선형 계획법 문제를 강한 볼록(strictly convex) 최적화 문제로 변환시키는데, 놀랍게도 이 문제의 해는 P^* = \text{diag}(u) K \text{diag}(v) 형태의 구조를 갖는다는 사실이 밝혀졌다.6 여기서

K는 비용 행렬로부터 유도된 커널 행렬이며, u와 v는 스케일링 벡터이다. 이 구조는 Sinkhorn-Knopp 알고리즘이 해결하고자 했던 행렬 스케일링 문제와 정확히 일치한다. 즉, 수십 년 전에 개발된 단순한 스케일링 알고리즘이, 이론적으로 변형된 최적 수송 문제를 푸는 매우 효율적인 해법임이 드러난 것이다. 이 발견은 최적 수송 이론을 기계 학습, 컴퓨터 비전, 자연어 처리 등 대규모 데이터를 다루는 현대 과학 기술 분야의 실용적인 핵심 도구로 변모시키는 기폭제가 되었다.3 알고리즘의 본질은 변하지 않았지만, 적용되는 문제의 패러다임이 바뀌면서 그 가치가 재발견된 것이다.

1.3 안내서의 구조와 전개 방향 제시

본 안내서는 Sinkhorn-Knopp 알고리즘의 다층적인 면모를 심도 있게 분석하는 것을 목표로 한다. 먼저 II장에서는 알고리즘의 수학적 기초를 다룬다. 행렬 스케일링 문제를 정의하고, 알고리즘의 반복적 절차를 설명하며, 수렴과 유일성을 보장하는 핵심 이론인 Sinkhorn-Knopp 정리를 상세히 분석한다. III장에서는 수렴 이론을 더욱 깊이 파고들어, 선형 수렴 속도의 정량적 분석과 행렬의 구조적 속성(밀도 등)이 수렴에 미치는 영향, 그리고 KL 발산을 이용한 현대적 수렴 분석 프레임워크를 탐구한다.

IV장에서는 본 알고리즘의 현대적 의의의 핵심인 최적 수송 이론과의 근본적인 연결고리를 상세히 유도한다. 엔트로피 정규화 개념을 소개하고, 쌍대 문제(dual problem)를 통해 Sinkhorn 알고리즘이 자연스럽게 도출되는 과정을 보이며, ’Sinkhorn 거리’의 개념과 그 중요성을 논한다. V장에서는 계산적 측면과 실제적 구현에 초점을 맞춘다. 계산 복잡도를 기존 해법과 비교하고, 수치 안정성을 위한 로그-영역 변환, 그리고 Greenkhorn, \epsilon-스케일링, GPU 가속화 등 다양한 성능 향상 기법들을 체계적으로 정리한다.

VI장에서는 기계 학습을 중심으로 한 광범위한 현대적 응용 분야를 조망한다. 생성적 적대 신경망(GANs), 도메인 적응, 단어 임베딩 등 구체적인 사례를 통해 알고리즘이 어떻게 실용적인 문제 해결에 기여하는지 살펴본다. 마지막으로 VII장에서는 안내서의 내용을 종합하여 알고리즘의 학술적, 실용적 의의를 요약하고, 확장성, 제약 조건 문제 등 현재 진행 중인 연구 동향과 향후 과제를 제시하며 마무리한다.

2. Sinkhorn-Knopp 알고리즘의 수학적 기초

2.1 문제 정의: 행렬 스케일링과 이중 확률 행렬

Sinkhorn-Knopp 알고리즘의 근본적인 목표는 행렬 스케일링 문제의 해결에 있다. 가장 기본적인 형태의 문제는 주어진 음이 아닌 정방 행렬 A (A \in \mathbb{R}^{n \times n}, A_{ij} \ge 0)에 대해, 양의 대각 성분을 갖는 두 대각 행렬 D와 E를 찾아, 스케일링된 행렬 P = DAE가 이중 확률 행렬(doubly stochastic matrix)이 되도록 만드는 것이다.2 이중 확률 행렬이란 다음 두 조건을 만족하는 음이 아닌 행렬 P를 지칭한다.3

1. 모든 행의 합이 1이다: \sum_{j=1}^n P_{ij} = 1 for all i = 1, \dots, n.
2. 모든 열의 합이 1이다: \sum_{i=1}^n P_{ij} = 1 for all j = 1, \dots, n.

이는 벡터 표기법으로 P\mathbf{1} = \mathbf{1} 및 P^T\mathbf{1} = \mathbf{1}로 간결하게 표현할 수 있으며, 여기서 \mathbf{1}은 모든 원소가 1인 벡터이다.

이 문제는 더 일반적인 행렬 스케일링 문제의 특수한 경우로 확장될 수 있다. 일반적인 문제에서는 스케일링된 행렬 P의 행과 열의 합이 각각 미리 주어진 양의 벡터 r (r \in \mathbb{R}_+^n)과 c (c \in \mathbb{R}_+^m)를 만족하도록 하는 것을 목표로 한다.9 이 경우, \sum_{i=1}^n r_i = \sum_{j=1}^m c_j라는 조건이 필요하며, 이러한 스케일링이 가능한 행렬 A를 (r, c)-scalable 하다고 한다. 이중 확률 행렬 문제는 n=m이고 r=c=\mathbf{1}인 특수한 경우에 해당한다.

2.2 알고리즘의 반복적 절차

Sinkhorn-Knopp 알고리즘의 절차는 그 목표에 비해 놀라울 정도로 단순하고 직관적이다. 핵심 아이디어는 행렬의 모든 행 합을 목표치(예: r)에 맞추도록 정규화하고, 그 결과로 얻어진 행렬의 모든 열 합을 목표치(예: c)에 맞추도록 정규화하는 과정을 수렴할 때까지 번갈아 반복하는 것이다.2

이 과정은 스케일링 대각 행렬 D와 E를 직접 계산하는 대신, 이들의 대각 성분으로 구성된 스케일링 벡터 u와 v를 반복적으로 갱신하는 방식으로 효율적으로 구현된다. k번째 반복에서 P^{(k)} = \text{diag}(u^{(k)}) A \text{diag}(v^{(k)})라 할 때, 다음 단계의 갱신 규칙은 다음과 같이 주어진다.10

1. 열 정규화 (v 갱신): 먼저 현재의 행 스케일링 벡터 u^{(k)}를 고정한 채, 열의 합이 목표 벡터 c가 되도록 v를 갱신한다.
   v^{(k+1)} = c \./ \ (A^T u^{(k)})
   여기서 ./는 원소별 나눗셈(element-wise division)을 의미한다.

2. 행 정규화 (u 갱신): 다음으로, 새롭게 갱신된 열 스케일링 벡터 v^{(k+1)}을 사용하여 행의 합이 목표 벡터 r이 되도록 u를 갱신한다.
   u^{(k+1)} = r \./ \ (A v^{(k+1)})
   이 두 단계를 하나의 반복 주기로 하여, u와 v가 더 이상 변하지 않거나 변화량이 미리 설정된 허용 오차(tolerance)보다 작아질 때까지 반복한다.3

이러한 반복적 절차는 기하학적으로 두 볼록 집합(convex sets) 사이를 번갈아 사영(projection)하는 과정으로 해석될 수 있다.12 여기서 한 볼록 집합은 행 합 제약조건(

P\mathbf{1} = r)을 만족하는 모든 행렬의 공간이고, 다른 하나는 열 합 제약조건(P^T\mathbf{1} = c)을 만족하는 모든 행렬의 공간이다. 알고리즘의 각 단계는 현재의 행렬을 이 두 제약 공간 중 하나에 순차적으로 사영시키는 것과 같다. 이 교대 사영 과정은 결국 두 볼록 집합의 교집합, 즉 두 제약조건을 모두 만족하는 목표 행렬로 수렴하게 된다.12

2.3 핵심 이론: Sinkhorn-Knopp 정리

알고리즘의 단순함 이면에는 그 수렴과 해의 유일성을 보장하는 깊이 있는 수학적 이론이 존재한다. 이는 Sinkhorn-Knopp 정리에 의해 체계화되었으며, 행렬의 0이 아닌 원소들의 구조적 패턴, 즉 조합론적 속성이 알고리즘의 행태를 결정한다는 중요한 사실을 밝힌다.

2.3.1 수렴 조건 - 완전 지지 (Total Support)

알고리즘이 수렴하고, 목표하는 이중 확률 행렬 P가 존재하기 위한 필요충분조건은 행렬 A가 **‘완전 지지(total support)’**를 갖는 것이다.13 ’완전 지지’란 행렬

A의 0이 아닌 모든 원소가 적어도 하나의 양의 대각선(positive diagonal) 상에 위치할 수 있음을 의미한다. 여기서 양의 대각선이란 순열 \sigma에 대해 \prod_{i=1}^n A_{i, \sigma(i)} > 0을 만족하는 대각선을 말한다. 다시 말해, A의 행과 열을 적절히 재배열하여 주대각선 성분이 모두 0이 아니게 만들 수 있는 순열이 존재해야 한다. 만약 A가 0으로만 구성된 행이나 열을 포함하고 있다면, 해당 행이나 열의 합을 0이 아닌 값으로 만드는 것은 불가능하므로 알고리즘은 수렴할 수 없다.3 따라서, 완전 지지는 알고리즘의 수렴성을 결정하는 근본적인 구조적 조건이다.

2.3.2 유일성 조건 - 완전 분해 불가능성 (Full Indecomposability)

행렬 A가 완전 지지를 갖는다면, 스케일링을 통해 얻어지는 이중 확률 행렬 P는 유일하게 존재한다.13 더 나아가, 이 변환을 수행하는 스케일링 대각 행렬 D와 E가 스칼라 곱(즉, D_1 = \alpha D_2, E_1 = (1/\alpha) E_2 for some \alpha > 0)을 제외하고 유일하게 결정되기 위한 필요충분조건은 A가 **‘완전 분해 불가능(fully indecomposable)’**한 것이다.13

완전 분해 불가능 행렬이란, 어떠한 순열 행렬 P와 Q를 사용하더라도 PAQ를 다음과 같은 블록 행렬 형태로 만들 수 없는 행렬을 의미한다 13:
PAQ = \begin{bmatrix} A_1 & 0 \\ A_2 & A_3 \end{bmatrix}
여기서 A_1과 A_3는 정방 행렬이다. 이 조건은 행렬 내의 모든 부분 집합 간에 상호 연결성이 존재하여, 행렬을 독립적인 블록으로 분리할 수 없음을 보장한다. 만약 행렬이 분해 가능하다면, 각 블록은 독립적으로 스케일링될 수 있어 스케일링 행렬의 유일성이 보장되지 않는다.

이처럼, Sinkhorn-Knopp 알고리즘의 수렴성과 해의 유일성은 입력 행렬의 수치적 값보다는 그 값들의 구조적 배치, 즉 0과 0이 아닌 원소들의 조합론적 패턴에 의해 근본적으로 결정된다. 이는 문제의 해결 가능성이 특정 값의 크기가 아닌, 시스템의 연결 구조에 달려있음을 시사하는 중요한 통찰이다. 따라서 알고리즘을 적용하기 전에 입력 행렬의 구조를 분석하는 것이 매우 중요하며, 실제 응용에서는 종종 행렬의 모든 원소에 아주 작은 양수(\epsilon)를 더하여 완전 지지 및 완전 분해 불가능성 조건을 인위적으로 만족시킴으로써 수렴을 보장하기도 한다.

3. 수렴 이론 심층 분석

3.1 수렴 속도: 선형 수렴성

Sinkhorn-Knopp 알고리즘의 중요한 이론적 성질 중 하나는 수렴 속도가 선형적(linear)이라는 점이다.13 선형 수렴은 알고리즘의 반복 과정에서 오차(error)가 일정한 비율, 즉 수렴률(rate of convergence) \rho < 1에 따라 기하급수적으로 감소함을 의미한다. k번째 반복에서의 오차를 e_k라 할 때, e_{k+1} \approx \rho \cdot e_k 관계가 성립한다. 이는 알고리즘이 수치적으로 안정적이며, 수렴에 필요한 반복 횟수를 예측 가능하게 만든다.

초기 연구는 Soules에 의해 이루어졌으며, 그는 알고리즘을 행렬에 대한 고정점 반복(fixed-point iteration)으로 간주하고 야코비 행렬(Jacobian matrix)을 분석하여 완전 지지를 갖는 행렬에 대해 선형 수렴성을 증명했다.13 그러나 이 연구는 수렴률의 구체적인 값을 제시하지는 못했다. 이후 Franklin과 Lorenz는 모든 원소가 양수인 행렬(A > 0)에 대해 Hilbert의 사영 계량(projective metric)이라는 도구를 사용하여 수렴률의 상한(upper bound)을 명시적으로 제시했다.13 그들이 제시한 상한은 다음과 같다:
C = \left( \frac{\sqrt{\theta(A)} - 1}{\sqrt{\theta(A)} + 1} \right)^2, \quad \text{where} \quad \theta(A) = \max_{i,j,k,l} \frac{A_{ik}A_{jl}}{A_{jk}A_{il}}
이 상한은 이론적으로 중요하지만, 행렬 A의 가장 작은 원소가 0에 가까워지면 \theta(A)가 무한대에 가까워져 상한 C가 1에 수렴하게 된다. 이는 희소하거나 0에 가까운 값을 포함하는 행렬에 대해서는 실제 수렴 속도를 제대로 예측하지 못하는 한계를 지닌다.14

3.2 수렴률의 정량화: 특이값과 행렬 밀도

보다 정밀하고 일반적인 수렴률 분석은 알고리즘의 결과물인 이중 확률 행렬 P의 스펙트럼 속성(spectral properties)과 직접적으로 연결된다. 완전 분해 불가능한 행렬 A에 대해, Sinkhorn-Knopp 알고리즘의 점근적 수렴률은 결과 행렬 P의 두 번째로 큰 특이값(second largest singular value), \sigma_2(P)의 제곱, 즉 \sigma_2(P)^2에 의해 정확하게 결정된다는 사실이 밝혀졌다.13 이중 확률 행렬의 가장 큰 특이값은 항상 \sigma_1(P) = 1이므로, \sigma_2(P)는 1과의 간격(gap)을 나타내며, 이 간격이 클수록(즉, \sigma_2(P)가 작을수록) 수렴이 빨라진다. 이 결과는 알고리즘의 동역학이 최종적으로 도달하는 평형 상태의 구조적 특성에 의해 지배됨을 보여주는 심오한 연결고리이다.

최근의 연구는 이러한 분석을 한 단계 더 발전시켜, 행렬의 ’밀도(density)’라는 개념을 도입하여 수렴 속도를 더욱 세밀하게 규명했다.17 여기서 정규화된 행렬의 밀도 \gamma는 행이나 열에 특정 임계값 이상의 값을 갖는 원소의 비율로 정의된다. 이 연구에 따르면, 밀도 \gamma가 1/2을 초과할 경우, 알고리즘은 \mathcal{O}(\log n - \log \varepsilon)라는 매우 빠른 반복 횟수 내에 \varepsilon-근사 해를 찾을 수 있다.17 이는 행렬이 조밀할수록, 즉 0이 아닌 유의미한 값을 갖는 원소가 많을수록 수렴에 필요한 반복 횟수가 줄어든다는 것을 의미한다.

이 발견은 기존의 직관, 즉 희소한 행렬이 처리할 데이터가 적어 더 빠를 것이라는 생각과 상반되는 중요한 결과를 제시한다.18 조밀한 행렬은 행과 열 간의 정보를 전달하는 ’경로’가 더 많기 때문에, 스케일링 과정에서 시스템 전체가 평형 상태(이중 확률 상태)에 더 빨리 도달할 수 있다. 반면, 희소한 행렬은 정보 흐름에 병목 현상을 일으켜 수렴을 지연시킬 수 있다.

더욱 흥미로운 점은, 밀도 \gamma = 1/2에서 급격한 상전이(phase transition)가 발생한다는 것이다. 밀도가 1/2 미만인 특정 행렬에 대해서는 알고리즘이 수렴하는 데 \Omega(\sqrt{n}/\varepsilon)의 반복 횟수가 필요할 수 있음이 증명되었다.17 이는 알고리즘의 성능이 행렬의 밀도에 따라 질적으로 달라질 수 있음을 시사하며, 실제 문제에 알고리즘을 적용할 때 단순히 비-영 원소의 개수(nnz(A))를 줄이는 희소화 전략이 항상 최선이 아닐 수 있음을 경고한다. 각 반복의 계산 비용은 줄어들지만, 총 반복 횟수가 폭발적으로 증가하여 전체 계산 시간이 오히려 늘어날 수 있기 때문이다.

3.3 KL 발산을 이용한 현대적 수렴 분석

현대적인 최적화 이론의 관점에서 Sinkhorn-Knopp 알고리즘의 수렴을 분석하는 가장 강력한 도구 중 하나는 쿨백-라이블러 발산(Kullback-Leibler divergence, KL 발산)이다.9 이 접근법은 알고리즘의 각 반복 단계를 현재의 행/열 합 분포와 목표 분포 사이의 KL 발산을 최소화하는 과정으로 재해석한다.19

구체적으로, Sinkhorn 알고리즘은 엔트로피 정규화 최적 수송 문제의 쌍대 문제(dual problem)에 대한 블록 좌표 상승(block coordinate ascent) 방법과 동일한 것으로 볼 수 있다.20 각 반복 단계에서 하나의 쌍대 변수 집합(예: 행 스케일링 벡터에 해당하는 변수)을 고정한 채 다른 변수 집합에 대해 목적 함수를 최대화하는데, 이 과정이 바로 KL 발산의 사영(projection)으로 표현된다. 이러한 관점은 리아푸노프 함수(Lyapunov function)를 정의하여 알고리즘이 매 단계마다 목적 함수 값을 단조적으로 개선함을 보이고, 이를 통해 수렴을 증명하는 강력한 이론적 틀을 제공한다.19

이 분석의 또 다른 장점은 KL 발산과 다른 오차 측정 기준(error metrics) 간의 관계를 통해 실제적인 수렴률을 유도할 수 있다는 점이다. 예를 들어, 핀스커의 부등식(Pinsker’s inequality)은 KL 발산과 \ell_1 거리 사이에 다음과 같은 관계를 설정한다 19:
D_{KL}(p \Vert q) \ge \frac{1}{2} \Vert p - q \Vert_1^2
이를 통해 KL 발산의 수렴률로부터 \ell_1 오차, 즉 실제 행/열 합과 목표 합 사이의 차이에 대한 수렴률을 직접 유도할 수 있다.19 이러한 분석 기법은 이전 연구들이 주로 유계 비용(bounded cost)을 가정했던 것과 달리, 무계 비용(unbounded cost)을 갖는 더 일반적인 경우에도 적용 가능하다. 예를 들어, 2차 비용 함수(c(x,y) = \Vert x-y \Vert^2)와 같은 중요한 사례에 대해 \mathcal{O}(1/t)의 수렴률을 증명함으로써, 알고리즘의 성능을 더 넓은 범위의 문제에 대해 이론적으로 보장한다.21

4. 최적 수송 이론과의 연결

4.1 엔트로피 정규화 최적 수송

Sinkhorn-Knopp 알고리즘의 현대적 가치는 최적 수송(Optimal Transport, OT) 이론과의 깊은 연결에서 비롯된다. 고전적인 이산 최적 수송 문제는 한 이산 확률 분포 r을 다른 분포 c로 옮기는 데 필요한 최소 비용을 찾는 문제로, 다음과 같은 선형 계획법(Linear Programming, LP)으로 정식화된다 4:
\min_{P \in U(r,c)} \langle P, C \rangle
여기서 C는 비용 행렬로, C_{ij}는 r의 i번째 요소에서 c의 j번째 요소로 단위 질량을 옮기는 데 드는 비용을 나타낸다. P는 수송 계획(transport plan) 행렬이며, \langle P, C \rangle = \sum_{i,j} P_{ij}C_{ij}는 총 수송 비용이다. U(r,c)는 r과 c를 각각 행과 열의 합(marginal)으로 갖는 모든 음이 아닌 행렬들의 집합, 즉 수송 폴리토프(transport polytope)이다.4

이 LP 문제는 해가 일반적으로 매우 희소(sparse)하며, 계산 비용이 높아 대규모 문제에 적용하기 어렵다. 이 한계를 극복하기 위해 엔트로피 정규화(entropic regularization)라는 기법이 도입되었다. 이는 원래의 목적 함수에 수송 계획 P의 섀넌 엔트로피(Shannon entropy) 항을 추가하는 것이다 22:
\min_{P \in U(r,c)} \langle P, C \rangle - \varepsilon H(P)
여기서 H(P) = -\sum_{i,j} P_{ij} \log(P_{ij})이며, \varepsilon > 0는 정규화의 강도를 조절하는 파라미터이다. 이 엔트로피 항은 P의 원소들이 0에 가깝게 집중되는 것을 막는 ‘장벽(barrier)’ 역할을 하여, 수송 계획을 더 부드럽고 조밀하게 만든다. 수학적으로 더 중요한 것은, 이 정규화 항이 목적 함수를 강한 볼록(strictly convex) 함수로 만들어 문제의 해가 유일하게 존재하도록 보장한다는 점이다.4

4.2 쌍대 문제로부터 Sinkhorn 알고리즘 유도

엔트로피 정규화 OT 문제와 Sinkhorn 알고리즘 사이의 연결고리는 라그랑주 쌍대성(Lagrangian duality)을 통해 명확하게 드러난다. 이 원리는 두 세계를 잇는 수학적 다리 역할을 하며, Sinkhorn 알고리즘이 단순한 행렬 스케일링 절차를 넘어 정규화 OT 문제를 푸는 원리적인 최적화 알고리즘임을 보여준다.

유도 과정은 다음과 같다. 먼저, 엔트로피 정규화 OT 문제의 제약조건(P\mathbf{1} = r과 P^T\mathbf{1} = c)을 라그랑주 승수(Lagrange multiplier) \phi와 \psi를 사용하여 목적 함수에 포함시킨다. 이 라그랑지안을 수송 계획 P에 대해 최소화하면, 최적의 수송 계획 P^*가 쌍대 변수 \phi, \psi와 비용 행렬 C에 의해 다음과 같은 닫힌 형태(closed-form)로 표현됨을 보일 수 있다 6:
P^*_{ij} = \exp\left( \frac{\phi_i + \psi_j - C_{ij}}{\varepsilon} \right)
여기서 쌍대 변수 \phi와 \psi는 ’슈뢰딩거 포텐셜(Schrödinger Potentials)’이라고도 불린다.22 이들은 OT 문제의 기하학적 구조에 대한 깊은 정보를 담고 있다.

이 해를 지수 함수와 행렬 형태로 재구성하면 다음과 같이 쓸 수 있다:
P^* = \text{diag}(u) K \text{diag}(v)
여기서 커널 행렬(kernel matrix) K = \exp(-C/\varepsilon)이고, 스케일링 벡터 u = \exp(\phi/\varepsilon)와 v = \exp(\psi/\varepsilon)이다.6 즉, 정규화 OT 문제의 최적 해는 특정 커널 행렬 K를 스케일링하여 얻어진다.

마지막으로, 이 최적 해 P^*가 원래의 행/열 합 제약조건, 즉 P^*\mathbf{1} = r과 (P^*)^T\mathbf{1} = c를 만족해야 한다는 사실을 이용한다. 이 두 방정식을 u와 v에 대해 정리하면 다음과 같은 고정점 반복(fixed-point iteration) 관계식을 얻는다:
u = r \./ \ (Kv) \quad \text{and} \quad v = c \./ \ (K^T u)
이 반복식은 다름 아닌, 행렬 K를 입력으로 하고 목표 행/열 합으로 r과 c를 사용하는 Sinkhorn-Knopp 알고리즘과 정확히 동일하다.6

결론적으로, Sinkhorn 알고리즘은 엔트로피 정규화 OT 문제의 쌍대 문제를 푸는 블록 좌표 상승법(block coordinate ascent)과 같다.21 각 반복 단계는 하나의 쌍대 변수 집합(예: \phi)을 고정한 채 다른 변수 집합(\psi)에 대해 쌍대 목적 함수를 최대화하는 과정에 해당하며, 이는 스케일링 벡터를 갱신하는 연산으로 나타난다. 이 발견은 Sinkhorn 알고리즘에 강력한 이론적 기반을 제공하며, 스케일링 벡터 u와 v가 임의의 숫자가 아니라 문제의 쌍대 해와 직접적으로 연결된 의미 있는 값임을 밝혀준다.

4.3 Sinkhorn 거리

엔트로피 정규화 OT 문제의 최적값, 즉 \min_{P \in U(r,c)} \langle P, C \rangle - \varepsilon H(P), 그 자체로 두 확률 분포 r과 c 사이의 유용한 유사도 척도로 사용될 수 있다. 이를 ‘Sinkhorn 거리(Sinkhorn Distance)’ 또는 ’엔트로피 정규화 바서슈타인 거리(entropy-regularized Wasserstein distance)’라고 부른다.4

Sinkhorn 거리는 고전적인 바서슈타인 거리를 근사하지만, 계산적으로 훨씬 효율적이라는 장점 외에도 매우 중요한 성질을 하나 더 가지고 있다: 바로 정규화 파라미터 \varepsilon > 0에 대해 **미분 가능(differentiable)**하다는 것이다.23 원래의 바서슈타인 거리는 미분 불가능한 지점이 존재하여 경사 하강법(gradient descent) 기반의 최적화 알고리즘에 직접 사용하기 어렵다. 반면, Sinkhorn 거리는 입력 분포 r, c 및 비용 행렬 C에 대해 미분이 가능하며, 그 기울기(gradient) 또한 Sinkhorn 알고리즘의 결과물(최적 쌍대 변수)을 통해 쉽게 계산할 수 있다.

이 미분 가능성은 Sinkhorn 거리가 현대 기계 학습, 특히 심층 신경망(deep neural networks) 훈련의 판도를 바꾸는 계기가 되었다. Sinkhorn 거리를 손실 함수(loss function)로 직접 사용하여 모델의 파라미터를 최적화할 수 있게 된 것이다.1 이는 모델이 생성하는 출력 분포와 실제 데이터 분포 사이의 기하학적 거리를 직접 최소화하도록 훈련하는 것을 가능하게 하여, 생성 모델, 도메인 적응 등 다양한 분야에서 획기적인 성능 향상을 이끌었다.

5. 계산적 측면과 실제적 구현

5.1 계산 복잡도: 선형 계획법과의 비교

Sinkhorn-Knopp 알고리즘의 가장 큰 실용적 장점은 계산 효율성에 있다. 고전적 최적 수송(OT) 문제는 본질적으로 선형 계획법(LP) 문제로, 이를 해결하기 위한 표준 알고리즘인 네트워크 심플렉스(network simplex)나 내부점법(interior-point methods)은 n개의 점을 갖는 분포에 대해 대략 \mathcal{O}(n^3 \log n)의 계산 복잡도를 갖는다.4 이 복잡도는 n이 수천을 넘어가면 현실적으로 계산이 불가능한 수준으로, 대규모 데이터셋에 대한 OT의 적용을 가로막는 주된 장벽이었다.

반면, Sinkhorn 알고리즘은 훨씬 낮은 계산 복잡도를 자랑한다. 알고리즘의 각 반복 단계는 주로 n \times n 크기의 커널 행렬 K와 n차원 벡터 간의 곱셈 연산으로 구성된다. 따라서 한 번의 반복에 필요한 계산량은 \mathcal{O}(n^2)이다.8 만약 알고리즘이 L번의 반복 후에 수렴한다고 가정하면, 총 계산 복잡도는 \mathcal{O}(L \cdot n^2)가 된다. 수렴에 필요한 반복 횟수 L은 정규화 파라미터 \varepsilon와 정확도 요구사항에 따라 달라지며, 이론적인 최악의 경우 복잡도 상한은 \mathcal{O}(n^2/\varepsilon^2)와 같이 \varepsilon에 대해 다항식적으로 나쁘게 나타날 수 있다.29 하지만 실제 응용에서는 L이 n이나 \varepsilon에 비해 훨씬 작아, LP 해법보다 수십에서 수백 배, 때로는 그 이상 빠른 속도를 보인다.4 이러한 압도적인 속도 차이가 Sinkhorn 알고리즘을 대규모 OT 문제의 사실상 표준 해법으로 만들었다.

5.2 수치 안정성 문제와 로그-영역 변환

Sinkhorn 알고리즘의 빠른 속도에도 불구하고, 실제 구현 시에는 중요한 문제에 직면하게 되는데, 바로 수치적 불안정성(numerical instability)이다. 이 문제는 정규화 파라미터 \varepsilon가 작아질 때 특히 심각해진다. \varepsilon가 0에 가까워질수록 엔트로피 정규화 OT 문제는 원래의 비-정규화 OT 문제에 가까워지지만, 커널 행렬 K = \exp(-C/\varepsilon)의 원소 값들이 극단적으로 커지거나 작아지게 된다. 비용 C_{ij}가 큰 항목에 대해서는 K_{ij}가 부동소수점 정밀도의 한계로 인해 0으로 처리(언더플로우, underflow)되고, 비용이 작은 항목에 대해서는 무한대로 처리(오버플로우, overflow)될 수 있다.3 이는 알고리즘의 반복 과정에서 0으로 나누는 연산을 유발하거나 정밀도를 상실시켜 완전히 잘못된 결과를 낳게 한다.

이 문제를 해결하기 위한 표준적인 기법은 **‘로그-영역(log-domain)’**에서 알고리즘을 수행하는 것이다.3 이는 스케일링 벡터 u, v를 직접 다루는 대신, 이들의 로그 값인 쌍대 변수 \phi = \varepsilon \log u와 \psi = \varepsilon \log v를 직접 갱신하는 방식이다. 곱셈과 나눗셈 연산은 덧셈과 뺄셈으로 변환되며, 수치적으로 불안정한 행렬-벡터 곱셈 Kv는 다음과 같은 안정적인 log-sum-exp 연산으로 대체된다:
(\text{LSE}(M))_i = \log \sum_j \exp(M_{ij})
로그-영역에서의 Sinkhorn 반복식은 다음과 같이 표현될 수 있다 21:

1. \psi^{(k+1)} = -\varepsilon \cdot \text{LSE}_{j} \left( (\phi^{(k)}_i - C_{ij})/\varepsilon \right) + \text{const}
2. \phi^{(k+1)} = \varepsilon \log r - \varepsilon \cdot \text{LSE}_{j} \left( (\psi^{(k+1)}_j - C_{ij})/\varepsilon \right)

이 변환은 \exp 함수의 인자로 들어가는 값들의 범위를 효과적으로 제어하여 언더플로우와 오버플로우를 방지하고, 작은 \varepsilon 값에 대해서도 알고리즘이 안정적으로 작동하도록 보장한다.

5.3 알고리즘 가속 기법

표준 Sinkhorn 알고리즘의 성능을 더욱 향상시키기 위해 다양한 가속 기법들이 제안되었다. 이러한 기법들은 수렴에 필요한 반복 횟수를 줄이거나 각 반복의 계산 비용을 낮추는 데 초점을 맞춘다.

• Greenkhorn: 매 반복마다 모든 행과 열을 갱신하는 대신, 현재 제약조건을 가장 많이 위반하는, 즉 오차가 가장 큰 단일 행 또는 열을 선택하여 갱신하는 탐욕적(greedy) 방식이다. 이는 중요한 업데이트에 계산을 집중함으로써 종종 표준 Sinkhorn보다 훨씬 적은 총 연산으로 수렴에 도달한다.8

• \varepsilon-스케일링 ($\varepsilon$-scaling): \varepsilon가 클수록 정규화 효과가 강해져 문제가 더 부드러워지고 풀기 쉬워진다. \varepsilon-스케일링은 이러한 성질을 이용하는 휴리스틱으로, 처음에는 큰 \varepsilon 값으로 문제를 빠르게 푼 뒤, 그 해를 초기값으로 삼아 점차 \varepsilon을 목표값까지 줄여가며 문제를 푸는 방식이다. 각 단계에서 좋은 초기값을 가지고 시작하므로 총 반복 횟수를 크게 줄일 수 있다.31

• 가속 및 모멘텀 (Acceleration and Momentum): Nesterov 가속이나 Anderson 가속과 같은 고전적인 최적화 기법을 Sinkhorn 반복에 적용하여 수렴 속도를 개선하려는 시도도 있다.34 또한, Bregman 사영 연산자를 이완(overrelax)시켜 각 단계에서 더 큰 보폭으로 업데이트함으로써 더 빠른 수렴을 유도하는 Over-relaxed Sinkhorn 기법도 제안되었다.35

• GPU 병렬화: 알고리즘의 핵심 연산이 행렬-벡터 또는 행렬-행렬 곱셈이라는 점은 GPU(Graphics Processing Unit)를 이용한 대규모 병렬 처리에 매우 유리하게 작용한다.4 단일 명령 다중 데이터(SIMD) 아키텍처를 활용하여

\mathcal{O}(n^2) 연산을 동시에 수행함으로써, 대규모 문제 해결 시간을 획기적으로 단축시킬 수 있다. 이는 Sinkhorn 알고리즘이 현대 기계 학습 분야에서 널리 채택된 가장 중요한 실용적 이유 중 하나이다.

• 커널 행렬 근사: n이 매우 클 때 \mathcal{O}(n^2)의 복잡도조차 부담이 될 수 있다. 이를 해결하기 위해 커널 행렬 K 자체를 근사하는 방법이 연구되었다. Nyström 방법을 사용하여 K를 저-순위(low-rank) 행렬로 근사하거나 26, 중요한 일부 원소만 샘플링하여 희소 행렬(sparse matrix)로 만드는 희소화(sparsification) 기법을 통해 28 각 반복의 계산 비용을

\mathcal{O}(nr) (r은 순위) 또는 \mathcal{O}(s) (s는 0이 아닌 원소 수)로 크게 줄일 수 있다.

이러한 이론적, 공학적 개선의 순환은 Sinkhorn 알고리즘의 발전을 이끌어왔다. 수치적 불안정성이라는 실용적 문제가 로그-영역 변환이라는 이론적 해결책을 낳았고, 더 빠른 속도에 대한 요구는 Greenkhorn과 같은 알고리즘적 변형과 GPU 활용이라는 하드웨어적 해결책으로 이어졌다. 이처럼 이론과 실제가 상호작용하며 발전해 온 역사는 Sinkhorn 알고리즘이 강력하고 성숙한 계산 도구로 자리매김하게 된 배경을 잘 보여준다.

6. 주요 응용 분야 탐구

Sinkhorn-Knopp 알고리즘은 최적 수송 문제의 효율적인 근사 해법으로 자리매김하면서, 다양한 과학 및 공학 분야, 특히 데이터 기반의 기계 학습 분야에서 혁신적인 응용을 이끌어내고 있다. 여러 응용 분야에 걸쳐 공통적으로 나타나는 핵심적인 패러다임은, Sinkhorn 알고리즘을 단순히 오프라인 계산 도구로 사용하는 것을 넘어, 심층 신경망과 같은 복잡한 모델의 **‘미분 가능한 계층(differentiable layer)’**으로 통합하는 것이다. Sinkhorn 거리의 미분 가능성 덕분에, 전체 최적 수송 계산 과정을 역전파(backpropagation) 알고리즘에 포함시켜 종단간(end-to-end) 학습이 가능해진다. 이는 모델이 수송 비용의 관점에서 최적화된 표현(representation)이나 변환(transformation)을 학습하도록 유도하며, 기하학적 구조를 고려하는 새로운 차원의 모델링을 가능하게 한다.

6.1 기계 학습 (Machine Learning)

6.1.1 생성적 적대 신경망 (Generative Adversarial Networks, GANs)

GAN은 생성자(generator)와 판별자(discriminator)가 서로 경쟁하며 학습하는 생성 모델이다.36 전통적인 GAN은 Jensen-Shannon(JS) 발산이나 다른 f-발산을 최소화하도록 훈련되는데, 이는 생성된 데이터 분포와 실제 데이터 분포의 지지집합(support)이 겹치지 않을 경우 기울기 소실(vanishing gradients) 문제를 야기하여 훈련을 불안정하게 만들 수 있다. 바서슈타인 거리(Wasserstein distance)는 분포의 지지집합이 겹치지 않아도 유의미한 기울기를 제공하여 이러한 문제를 해결하며, Wasserstein GAN(WGAN)의 기반이 되었다. Sinkhorn 거리는 이 바서슈타인 거리를 미분 가능하고 계산적으로 효율적인 형태로 근사한 것으로, GAN의 손실 함수로 직접 사용될 수 있다.27 이를 통해 훈련 안정성을 높이고, 생성된 샘플의 질을 향상시키는 데 기여한다. 더 나아가, 바서슈타인 기하학에 기반한 자연 경사 하강법(natural gradient descent)을 Sinkhorn 알고리즘을 통해 근사하는 Sinkhorn Natural Gradient (SiNG)와 같은 연구는 더 효율적인 GAN 훈련 방법을 제시한다.27

6.1.2 도메인 적응 (Domain Adaptation)

도메인 적응은 레이블이 있는 소스 도메인(source domain)에서 학습한 모델을 레이블이 없는 타겟 도메인(target domain)에 일반화시키는 것을 목표로 한다.39 두 도메인 간의 데이터 분포 차이(distribution shift)가 주된 문제인데, 최적 수송은 이 문제를 해결하는 강력한 이론적 틀을 제공한다. 소스 도메인의 데이터 분포를 타겟 도메인의 분포로 ’수송’하는 최적의 계획을 찾아, 소스 데이터를 타겟 데이터의 분포에 맞게 변환(정렬)하는 것이다.39 Sinkhorn 알고리즘은 이 수송 계획을 대규모 데이터에 대해 효율적으로 계산하는 역할을 수행한다. 학습된 수송 계획을 통해 소스 데이터의 표현을 변환함으로써, 모델은 분포 차이에 강건해지고 타겟 도메인에서도 높은 성능을 발휘할 수 있게 된다.

6.2 자연어 처리 (Natural Language Processing)

6.2.1 단어 임베딩 (Word Embeddings)

단어 임베딩은 단어의 의미를 고차원 벡터 공간에 표현하는 기술이다. 최적 수송은 문서나 문장과 같이 단어들의 집합으로 구성된 텍스트 간의 의미적 유사도를 측정하는 새로운 방법을 제시한다. Word Mover’s Distance (WMD)는 한 문서를 다른 문서로 변환하는 데 필요한 최소 ‘이동’ 비용으로 문서 간의 거리를 정의한다. 여기서 각 단어는 임베딩 벡터로 표현되고, 단어 간의 이동 비용은 벡터 공간에서의 유클리드 거리로 계산된다. 전체 문서의 변환은 최적 수송 문제로 정식화되며, Sinkhorn 알고리즘은 이 WMD를 근사적으로 매우 빠르게 계산할 수 있게 해준다.42 이는 기존의 Bag-of-Words 모델이 단어 순서나 미묘한 의미 차이를 놓치는 단점을 극복하고, 문서 분류, 정보 검색, 기계 번역 평가 등에서 뛰어난 성능을 보인다.

6.3 컴퓨터 비전 및 데이터 과학

6.3.1 이미지 처리

이미지의 색상 분포는 픽셀 값들의 히스토그램으로 표현될 수 있다. 최적 수송은 한 이미지의 색상 히스토그램을 다른 이미지의 히스토그램으로 변환하는 최적의 방법을 찾아, 이미지 간 색상 전이(color transfer)나 스타일 변환을 수행하는 데 사용된다. 또한, 두 이미지의 유사도를 측정하는 기준으로도 활용될 수 있다.4 3D 점 구름(point cloud) 데이터 분석에서도, Sinkhorn 알고리즘은 점 구름 간의 대응 관계를 찾거나, 점 구름 데이터를 정규화된 형태로 변환하여 강건한 표현을 학습하는 데 응용된다.44

6.3.2 웹 페이지 랭킹

Sinkhorn-Knopp 알고리즘의 고전적인 응용 중 하나는 웹 페이지 랭킹이다. 웹 페이지 간의 하이퍼링크 구조를 인접 행렬(adjacency matrix)로 표현하고, 이 행렬에 Sinkhorn-Knopp 알고리즘을 적용하여 이중 확률 행렬로 변환할 수 있다. 이 결과 행렬의 정상 상태 분포(stationary distribution)는 각 페이지의 중요도나 권위를 나타내는 척도로 사용될 수 있으며, 이는 Google의 PageRank와 같은 다른 랭킹 알고리즘과 비교되는 대안적인 접근법을 제공한다.2

6.4 경제학 및 사회 과학

알고리즘의 기원이 된 행렬 스케일링은 경제학 및 사회 과학 분야에서 여전히 중요한 도구이다. 예를 들어, 국가 간의 무역 흐름을 나타내는 국제 무역 행렬이나, 특정 산업 부문 간의 상품 및 서비스 흐름을 나타내는 투입-산출표를 분석할 때, 행과 열의 합계가 특정 경제적 제약(예: 총 수출액, 총 수입액)을 만족하도록 데이터를 정규화하는 데 사용된다.3 사회 과학에서는 인구 이동이나 사회적 상호작용 패턴을 모델링하는 데에도 적용될 수 있다. 이러한 분야에서는 데이터의 일관성을 보장하고 균형 잡힌 분석을 수행하기 위한 전처리 단계로서 알고리즘이 활용된다.

7. 결론 및 향후 연구 방향

7.1 Sinkhorn-Knopp 알고리즘의 핵심적 의의 요약

본 안내서는 Sinkhorn-Knopp 알고리즘이 지난 반세기 동안 거쳐온 진화의 과정을 심층적으로 분석했다. 1960년대 행렬 스케일링이라는 특정 문제를 해결하기 위해 탄생한 이 단순한 반복 알고리즘은, 21세기에 들어 최적 수송 이론과의 극적인 만남을 통해 현대 계산 과학의 핵심 도구로 재탄생했다. 엔트로피 정규화라는 이론적 혁신이 기존에 계산적으로 다루기 어려웠던 최적 수송 문제를 Sinkhorn 알고리즘이 완벽하게 해결할 수 있는 형태로 변환시킨 것이다.

알고리즘의 핵심적 의의는 다음과 같이 요약될 수 있다. 첫째, 계산적 혁신을 가져왔다. \mathcal{O}(n^3 \log n)에 달하던 최적 수송 문제의 복잡도를 실질적으로 \mathcal{O}(n^2) 수준으로 낮추고, GPU 병렬화를 통해 대규모 문제에 대한 적용을 가능하게 했다. 둘째, 이론적 다리 역할을 했다. 행렬 스케일링과 최적 수송이라는 두 분야를 라그랑주 쌍대성이라는 원리를 통해 연결했으며, 이는 알고리즘에 강력한 이론적 정당성을 부여했다. 셋째, 기계 학습의 새로운 패러다임을 열었다. 미분 가능한 Sinkhorn 거리를 통해 최적 수송을 심층 신경망의 종단간 학습 프레임워크에 통합시킴으로써, 데이터의 기하학적 구조를 학습하는 새로운 세대의 모델들을 탄생시켰다. 이처럼 Sinkhorn-Knopp 알고리즘은 단순한 수치 해법을 넘어, 이론과 응용을 잇는 촉매제로서 현대 데이터 과학의 발전에 결정적인 기여를 했다.

7.2 현재 진행 중인 연구 및 미해결 과제 조망

Sinkhorn-Knopp 알고리즘은 이미 성숙한 기술이지만, 그 한계를 극복하고 적용 범위를 넓히기 위한 연구는 여전히 활발하게 진행 중이다. 향후 연구는 다음과 같은 방향으로 전개될 것으로 전망된다.

• 확장성(Scalability) 문제: \mathcal{O}(n^2)의 복잡도는 여전히 수백만 개 이상의 점을 갖는 초대규모 분포에는 부담이 된다. 커널 행렬 근사(Nyström, 희소화), 양자화(quantization), 그리고 특정 비용 구조(예: 1차원)를 활용한 동적 프로그래밍 기반의 선형 시간(\mathcal{O}(n)) 알고리즘 개발 등, 복잡도를 더욱 낮추려는 연구가 핵심적인 과제로 남아있다.28
• 제약 조건이 있는 OT (Constrained OT): 많은 실제 문제에서는 기본적인 행/열 합 제약 외에도 추가적인 선형 등식 또는 부등식 제약이 필요하다. 예를 들어, 특정 경로의 수송량을 제한하거나, 그룹별 수송 총량을 제어하는 경우이다. 이러한 복잡한 제약 조건을 효율적으로 처리하기 위한 새로운 Sinkhorn 유형의 알고리즘 개발이 중요한 연구 방향으로 부상하고 있다.7
• 불균형 최적 수송 (Unbalanced OT): 고전적 OT는 두 분포의 총 질량(mass)이 같아야 한다는 가정을 전제로 한다. 하지만 실제로는 생성되거나 소멸되는 질량이 존재할 수 있다. 총 질량이 다른 두 분포를 다루기 위한 불균형 최적 수송(Unbalanced Optimal Transport) 문제와 이를 해결하기 위한 Sinkhorn 알고리즘의 확장은 이론적으로나 응용적으로 매우 중요한 분야이다.28
• 이론적 이해의 심화: 알고리즘의 수렴률에 대한 분석은 상당한 진전을 이루었지만, 여전히 많은 미해결 문제가 남아있다. 특히 무계 비용 함수(unbounded cost functions)를 갖는 경우나, 이산 공간을 넘어 일반적인 확률 공간(general probability spaces)에서의 수렴률에 대한 더 정밀한 분석은 활발한 연구 주제이다.20 또한, 다양한 가속 기법들이 수렴에 미치는 영향을 이론적으로 규명하는 작업도 계속될 것이다.

결론적으로, Sinkhorn-Knopp 알고리즘은 앞으로도 계산적 최적 수송 분야의 중심축 역할을 계속할 것이며, 더 빠르고, 더 강건하며, 더 넓은 범위의 문제를 해결할 수 있는 차세대 알고리즘으로의 진화를 거듭할 것으로 기대된다.

8. 참고 자료

1. Sinkhorn’s theorem - Wikipedia, https://en.wikipedia.org/wiki/Sinkhorn%27s_theorem
2. Sinkhorn-Knopp algorithm for matrix normalisation - File Exchange - MATLAB Central, https://www.mathworks.com/matlabcentral/fileexchange/52930-sinkhorn-knopp-algorithm-for-matrix-normalisation
3. Implementing the Sinkhorn-Knopp Algorithm in NumPy - Statology, https://www.statology.org/implementing-the-sinkhorn-knopp-algorithm-in-numpy/
4. Sinkhorn Distances: Lightspeed Computation of Optimal Transport, http://papers.neurips.cc/paper/4927-sinkhorn-distances-lightspeed-computation-of-optimal-transport.pdf
5. Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn’s Algorithm - Proceedings of Machine Learning Research, http://proceedings.mlr.press/v80/dvurechensky18a/dvurechensky18a.pdf
6. Lecture 2: Entropic Optimal Transport - Luca Nenna, https://lucanenna.github.io/teaching/optimaltransport/lecture2.pdf
7. A Sinkhorn-type Algorithm for Constrained Optimal Transport - arXiv, https://arxiv.org/pdf/2403.05054
8. Quick start guide — POT Python Optimal Transport 0.9.6dev0 documentation, https://pythonot.github.io/master/quickstart.html
9. Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling, https://d-nb.info/1365338746/34
10. Federated Sinkhorn - arXiv, https://arxiv.org/html/2502.07021v1
11. Calculating transport plans with Sinkhorn-Knopp | regularize, https://regularize.wordpress.com/2015/09/17/calculating-transport-plans-with-sinkhorn-knopp/
12. Lecture 13: October 17 13.1 Sinkhorn’s Algorithm for Entropic Optimal Transport, https://www.math.ubc.ca/~geoff/courses/W2019T1/Lecture13.pdf
13. THE SINKHORN-KNOPP ALGORITHM: CONVERGENCE AND …, https://d-nb.info/991912322/34
14. THE SINKHORN-KNOPP ALGORITHM: CONVERGENCE AND APPLICATIONS ∗ 1. Introduction. If a graph has the appropriate structure, we can - Cerfacs, https://www.cerfacs.fr/algor/reports/2006/TR_PA_06_42.pdf
15. The Concepts of Irreducibility and Full Indecomposability of a Matrix in the Works of Frobenius, K6nig and Markov - Web.math.wisc.edu, https://people.math.wisc.edu/hans/paper_archive/other_papers/hs055.pdf
16. Combinatorial Orthogonality - University Digital Conservancy, https://conservancy.umn.edu/bitstreams/b4bd0f9d-cfce-4fac-8ff6-a7662c4b4f4b/download
17. [2507.09711] Phase transition of the Sinkhorn-Knopp algorithm - arXiv, https://arxiv.org/abs/2507.09711
18. Phase transition of the Sinkhorn-Knopp algorithm - arXiv, https://arxiv.org/pdf/2507.09711
19. Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. - CIS UPenn, https://www.cis.upenn.edu/~sanjeev/papers/sosa2018_sinkhorn.pdf
20. On the Linear Convergence of the Multimarginal Sinkhorn Algorithm - SIAM.org, https://epubs.siam.org/doi/10.1137/21M1410634
21. On the Convergence Rate of Sinkhorn’s Algorithm - Columbia Math Department, https://www.math.columbia.edu/~mnutz/docs/Sinkhorn_rate.pdf
22. Introduction to on Entropic Optimal Transport - Columbia Math …, https://www.math.columbia.edu/~mnutz/docs/EOT_lecture_notes.pdf
23. Entropy-Regularized Optimal Transport on Multivariate Normal and …, https://pmc.ncbi.nlm.nih.gov/articles/PMC8001134/
24. Regularized Optimal Transport - Michael Stanley, https://mihamerstan.github.io/pdfs/Regularized_Optimal_Transport.pdf
25. How to take the first derivative of the entropy-regularized Wasserstein distance?, https://math.stackexchange.com/questions/3867675/how-to-take-the-first-derivative-of-the-entropy-regularized-wasserstein-distance
26. Massively Scalable Sinkhorn Distances via the Nyström Method - NIPS, http://papers.neurips.cc/paper/8693-massively-scalable-sinkhorn-distances-via-the-nystrom-method.pdf
27. [PDF] Sinkhorn Natural Gradient for Generative Models - Semantic Scholar, https://www.semanticscholar.org/paper/Sinkhorn-Natural-Gradient-for-Generative-Models-Shen-Wang/4ec22ea248c306e1759b343541be5bea611088dc
28. Importance Sparsification for Sinkhorn Algorithm - Journal of Machine Learning Research, https://www.jmlr.org/papers/volume24/22-1311/22-1311.pdf
29. On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm - arXiv, https://arxiv.org/pdf/2002.03293
30. [1901.06482] On Efficient Optimal Transport: An Analysis of Greedy and Accelerated Mirror Descent Algorithms - arXiv, https://arxiv.org/abs/1901.06482
31. Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems - arXiv, https://arxiv.org/pdf/1610.06519
32. Quick start guide — POT Python Optimal Transport 0.9.5 documentation, https://pythonot.github.io/quickstart.html
33. Optimal Flow Transport and its Entropic Regularization: a GPU-friendly Matrix Iterative Algorithm for Flow Balance Satisfaction | OpenReview, https://openreview.net/forum?id=NtSlKEJ2DS
34. Rethinking Initialization of the Sinkhorn Algorithm - Proceedings of Machine Learning Research, https://proceedings.mlr.press/v206/thornton23a/thornton23a.pdf
35. [1711.01851] Overrelaxed Sinkhorn-Knopp Algorithm for Regularized Optimal Transport, https://arxiv.org/abs/1711.01851
36. Introduction | Machine Learning - Google for Developers, https://developers.google.com/machine-learning/gan
37. Generative Adversarial Network (GAN) - GeeksforGeeks, https://www.geeksforgeeks.org/deep-learning/generative-adversarial-network-gan/
38. Generative Adversarial Learning of Sinkhorn Algorithm Initializations - arXiv, https://arxiv.org/html/2212.00133v4
39. Optimal transport for Domain adaptation - CORE, https://core.ac.uk/download/pdf/52777330.pdf
40. Probability-Polarized Optimal Transport for Unsupervised Domain Adaptation, https://ojs.aaai.org/index.php/AAAI/article/view/29493/30815
41. Optimal Transport for Domain Adaptation through Gaussian Mixture Models - arXiv, https://arxiv.org/pdf/2403.13847?
42. Wasserstein Wormhole: Scalable Optimal Transport Distance with Transformers - arXiv, https://arxiv.org/html/2404.09411v1
43. [1910.11005] Wasserstein distances for evaluating cross-lingual embeddings - arXiv, https://arxiv.org/abs/1910.11005
44. Sinkhorn-Knopp algorithm (Python pseudocode). - ResearchGate, https://www.researchgate.net/figure/Sinkhorn-Knopp-algorithm-Python-pseudocode_fig2_378828010
45. The Sinkhorn–Knopp Algorithm: Convergence and Applications - SIAM.org, https://epubs.siam.org/doi/10.1137/060659624
46. A Linear Complexity Algorithm for Optimal Transport Problem with Log-type Cost - arXiv, https://arxiv.org/abs/2501.06578
47. [2403.05054] A Sinkhorn-type Algorithm for Constrained Optimal Transport - arXiv, https://arxiv.org/abs/2403.05054
48. A Sinkhorn-type Algorithm for Constrained Optimal Transport - OpenReview, https://openreview.net/forum?id=V5kCKFav9j